package com.problem.leetcode;


/**
 * TODO:总结思路 算法
 * @author yangzhuoleo
 * @Description ${Description}
 * @create 2018-01-02 22:38
 **/
public class Problem5 {
    public static void main(String[] args) {

        int i = 123321;
        int j = 1;
        System.out.println(i / 100000);
    }

    public String longestPalindrome(String s) {
        char[] chars  = init(s);
        int[]  values = new int[chars.length];
        int    mx     = 0;
        int    pos    = 0;

        for (int index = 0; index < chars.length; ++index) {
            values[index] = mx > index ? Math.min(values[2 * pos - index], mx - index) : 1;
            int begin = index - values[index];
            int end   = index + values[index];

            while (begin >= 0 && end < chars.length && chars[begin--] == chars[end++]) {
                ++values[index];
            }

            if (mx < (index + values[index])) {
                mx = index + values[index] - 1;
                pos = index;
            }
        }

        StringBuilder builder = getFinalString(chars, values);

        return builder.toString();

    }

    private StringBuilder getFinalString(char[] chars, int[] values) {
        int max      = 0;
        int tmpIndex = -1;
        for (int index = 0; index < values.length; ++index) {
            if (values[index] > max) {
                max = values[index];
                tmpIndex = index;
            }
        }

        StringBuilder builder = new StringBuilder();
        for (int index = tmpIndex - (max - 1); index <= tmpIndex + max - 1; ++index) {
            if (chars[index] != '#') {
                builder.append(chars[index]);
            }
        }
        return builder;
    }

    /**
     * 初始化字符串数组
     * @param s
     * @return
     */
    private char[] init(String s) {
        StringBuilder builder = new StringBuilder();
        for (int index1 = 0; index1 < s.length(); ++index1) {
            builder.append("#").append(s.charAt(index1));
        }
        builder.append("#");

        return builder.toString().toCharArray();
    }

}
